package exp10;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}


class SolutionAVL {
    ListNode root;

    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public void buildListFormArray(int[] array) { //构建不带头结点的链表
        root = new ListNode(array[0]);
        ListNode t = root;
        for (int i = 1; i < array.length; i++) {
            ListNode s = new ListNode(array[i]);
            t.next = s;
            t = t.next;
        }
    }
}


public class LinkedToAVL {
    public static void main(String[] args) {
        int[] array = {-10, -3, 0, 5, 9};
        SolutionAVL solution = new SolutionAVL();
        solution.buildListFormArray(array);
        TreeNode result = solution.sortedListToBST(solution.root);
        System.out.println(result.toString());
    }
}
